package com.openess.bigsearch.engine.utils.sort;

import java.util.Comparator;

public class ShellSort<E> implements Sort<E> {
	/**
	 * 希尔排序
	 * 
	 * @param array
	 * @param p
	 * @param r
	 */
	public void sort(E[] array, int p, int r, Comparator<? super E> c) {
		// 希尔和插入排序的主要不同就在于这外面一层循环。
		// 虽然因为delta将数组分成n组，但程序并不是在每个分组内进行单独的插入排序，其实还是整个数组顺序执行插入操作。
		// 也因为这种分组导致排序不稳定，因为两个相同的值可能分到了不同组。
		for (int delta = (r - p + 1) / 2; delta >= 1; delta /= 2) {
			for (int j = p + delta; j <= r; j++) {
				E key = array[j];
				int i = j - delta;
				// 在移位的过程中，确定正确的插入位置
				while (i >= p && c.compare(key, array[i]) < 0) {
					array[i + delta] = array[i];
					i -= delta;
				}
				// 一旦停止循环，说明当前位置的元素不符合要求，应该插入其前面一个位置
				array[i + delta] = key;
			}
		}
	}
}
